package edu.spbsu.nonsm00th.algorithms.sort.impl;

import edu.spbsu.nonsm00th.algorithms.sort.Comparator;
import edu.spbsu.nonsm00th.algorithms.sort.Sort;
import edu.spbsu.nonsm00th.model.enums.Ratio;
import java.util.List;

/**
 * Realization of QuickSort algorithm.
 * Result: increasing sequence.
 *
 * Worst case performance:       O(n2)
 * Best case performance:        O(nlogn)
 * Average case performance:     O(nlogn)
 * Worst case space complexity:  O(n)
 *
 * See: C.A.R. Hoare: Quicksort. Computer Journal, Vol. 5, 1, 10-15 (1962)
 *
 * @author mbuzdov
 */
public class QuickSort<T> implements Sort<T> {

    /**
     * {@inheritDoc}
     */
    public void sort(List<T> list, Comparator<T> comparator) {
        sort(list, 0, list.size()-1, comparator);
    }

    private void sort(List<T> list, int begin, int end, Comparator<T> comparator ) {
        if ( end <= begin ) {
            return;
        }
        int i = begin;
        int j = end;
        int iDelta = 0;
        int jDelta = 1;
        while ( i < j )
        {
            if ( Ratio.GREATER == comparator.compare(list.get(i), list.get(j) ) )
            {
                T temp = list.get(i);
                list.set(i, list.get(j));
                list.set(j, temp);

                int iTemp = iDelta;
                iDelta = jDelta;
                jDelta = iTemp;
            }
            j -= jDelta;
            i += iDelta;
        }
        sort(list, begin, i - 1, comparator);
        sort(list, i + 1, end, comparator);
    }

}
